#
# @lc app=leetcode.cn id=37 lang=python
#
# [37] 解数独
#

# @lc code=start
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.num_int = ['1','2','3','4','5','6','7','8','9']
        
        row_used = [set() for _ in range(9)]  # '1'
        col_used = [set() for _ in range(9)]
        box_used = [set() for _ in range(9)]

        for row in range(9):
            for col in range(9):
                num = board[row][col]
                if num in self.num_int:
                    row_used[row].add(num)
                    col_used[col].add(num)
                    box_used[row//3*3 + col//3].add(num)

        self.loop(0, 0, row_used, col_used, box_used)
        return self.board

    def loop(self, row, col, row_used, col_used, box_used):
        if row == 9:
            return True

        if col < 8:
            new_col = col+1
            new_row = row
        if col == 8:
            new_col = 0
            new_row = row+1

        if self.board[row][col] in self.num_int:
            if self.loop(new_row, new_col, row_used, col_used, box_used):
                return True

        else:
            for i in self.num_int:
                if (i in row_used[row]) or (i in col_used[col]) or (i in box_used[row//3*3 + col//3]):
                    continue
                self.board[row][col] = i
                row_used[row].add(self.board[row][col])
                col_used[col].add(self.board[row][col])
                box_used[row//3*3 + col//3].add(self.board[row][col])
                if self.loop(new_row, new_col, row_used, col_used, box_used):
                    return True

                row_used[row].remove(self.board[row][col])
                col_used[col].remove(self.board[row][col])
                box_used[row//3*3 + col//3].remove(self.board[row][col])
                self.board[row][col] = '.'

        
# @lc code=end

